package hot100;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/12 11:17
 */
public class lc76最小覆盖子串 {



    public String solve(String s1,String s2){

        String ans = "";
        int sa1[] = new int[60], sa2[] = new int[60];
        for (int i = 0; i < s2.length(); i++) {
            sa2[getIndex(s2.charAt(i))]++;
        }
        long count2 = Arrays.stream(sa2).filter(x -> x != 0).count();
        long count1 = 0;
        int l = 0, r= 0;
        while(r < s1.length()){
            int c = getIndex(s1.charAt(r));
            sa1[c]++;
            if(sa1[c] == sa2[c]){ // 这里不是 >= 而是 ==
                count1++;
            }
            // 判断窗口 , 窗口怎么进行收缩，这是非常关键的判断
            //当达到条件的时候， 判断收缩的时候能不能取得最小值
            while(count1 == count2 && l < r){
                int c2 = getIndex(s1.charAt(l)); // 尝试开始收缩
                sa1[c2]--;
                if(sa2[c2] == 0 || sa1[c2] >= sa2[c2]){
                    l++;
                }else{
                    sa1[c2]++;
                    break;
                }
            }
            if(count1 == count2){
                if(ans.length() == 0|| ans.length() > r - l + 1){
                    ans = s1.substring(l, r + 1);
                }
            }

            r++;
        }
        return ans;
    }

    private int getIndex(char charAt) {
        return charAt <= 'Z' && charAt >= 'A' ? charAt - 'A': charAt - 'a' + 26;
    }

    @Test
    public void test(){
        String s = "ADOBECODEBANC", t = "ABC";
        String solve = solve(s, t);
        System.out.println(solve);
    }

}
